/*
 * One example for NOI CSP-J Lesson 7:
 * <https://courses.fmsoft.cn/plzs/noijunior-graph-and-graph-theory.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <iostream>           // for std::cout
#include <vector>             // for std::vector
#include <queue>              // for std::queue

using namespace std;

using adj_list = vector<vector<int>>;

// 从给定的起始顶点处执行 BFS
vector<int> bfs(adj_list& graph, int s = 0)
{
    // 获取个数
    int V = graph.size();

    // 用于保存遍历结果
    vector<int> res;

    // 创建队列用于跟踪遍历过程
    queue<int> q;

    // 初始化用于跟踪顶点是否已经被访问的 visited 矢量
    vector<bool> visited(V, false);

    // 标记起始节点被访问并排入队列
    visited[s] = true;
    q.push(s);

    // 若队列未空就继续循环
    while (!q.empty()) {

        // 执行出队操作，并将出队的顶点保存到 res 中。
        // 注意：亦可在此处调用回调函数来访问定点。
        int curr = q.front();
        q.pop();
        res.push_back(curr);

        // 处理出队顶点的所有邻接顶点：
        // 若该邻接顶点未被访问，则标记为访问并令其入队。
        for (int x : graph[curr]) {
            if (!visited[x]) {
                visited[x] = true;
                q.push(x);
            }
        }
    }

    // 返回结果
    return res;
}

int main()
{
    // 用邻接表定义一个图
    adj_list graph = {
        {1,2},
        {0,2,3},
        {0,4},
        {1,4},
        {2,3}
    };

    // 获得 BFS 结果
    vector<int> ans = bfs(graph);

    // 输出结果
    for (auto i:ans) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

